- Title
- A complexity dichotomy for finding disjoint solutions of vertex deletion problems
- Creator
- Fellows, Michael R.; Guo, Jiong; Moser, Hannes; Niedermeier, Rolf
- Relation
- 34th International Symposium on Mathematical Foundations of Computer Science (MFCS 2009). Mathematical Foundations of Computer Science 2009: 34th International Symposium Proceedings (High Tatras, Slovakia 24-28 August, 2009) p. 319-330
- Publisher Link
- http://dx.doi.org/10.1007/978-3-642-03816-7_28
- Publisher
- Springer Berlin
- Resource Type
- conference paper
- Date
- 2009
- Description
- We investigate the computational complexity of a general "compression task" centrally occurring in the recently developed technique of iterative compression for exactly solving NP-hard minimization problems. The core issue (particularly but not only motivated by iterative compression) is to determine the computational complexity of, given an already inclusion-minimal solution for an underlying (typically NP-hard) vertex deletion problem in graphs, to find a better disjoint solution. The complexity of this task is so far lacking a systematic study. We consider a large class of vertex deletion problems on undirected graphs and show that, except for few cases which are polynomial-time solvable, the others are NP-complete. This class includes problems such as vertex cover (here the corresponding compression task is decidable in polynomial time) or undirected feedback vertex set (here the corresponding compression task is NP-complete).
- Subject
- graphs; NP-hard minimization; computational complexity; vertex deletion; vertex cover; undirected feedback vertex set
- Identifier
- uon:8859
- Identifier
- http://hdl.handle.net/1959.13/919420
- Identifier
- ISBN:9783642038150
- Reviewed
- Hits: 2978
- Visitors: 2932
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|